#include <iostream>
#include <valarray>
#include <vector>
#include <string>
using namespace std;


class sl
{
public:
    sl()
    {
        r.push_back(0);
        r.push_back(1);
        r.push_back(2);
        _size = 2;
    }

    int print(int& n)
    {
        if (n <= _size)
        {
            return r[n];
        }
        while (_size < n)
        {
            r.push_back((r[_size] * 2 + r[_size - 1]) % 32767);
            ++_size;
        }
        return r[_size];
    }
private:

    vector<int> r;
    int _size;
};


int main() {
    int n;
    cin >> n;
    sl s;
    while (n--)
    {
        int n1;
        cin >> n1;
        cout << s.print(n1) << endl;
    }
    return 0;
}

int main() {
    string str;
    getline(cin, str);
    int arr[4] = { 0 };
    for (auto s : str)
    {
        if ((s >= 'a' && s <= 'z') || (s >= 'A' && s <= 'Z'))
        {
            arr[0]++;
        }
        else if (s == ' ')
        {
            arr[1]++;
        }
        else if (s >= '0' && s <= '9')
        {
            arr[2]++;
        }
        else
        {
            arr[3]++;
        }
    }
    for (auto s : arr)
    {
        cout << s << endl;
    }
    return 0;
}

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        int n = nums.size();
        vector<int> ret;
        for (int i = 0; i < n; i++)
        {
            if (i == 0)
            {
                ret.push_back(nums[i]);
            }
            else
            {
                ret.push_back(nums[i] + ret[i - 1]);
            }
        }
        return ret;
    }
};

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            if (i == 0 && target < nums[i])
            {
                return 0;
            }
            if (nums[i] >= target)
            {
                return i;
            }
        }
        return n;
    }
};

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = (int)nums.size();
        if (!n) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) 
        {
            int mid = (l + r) / 2;
            if (nums[mid] == target) return mid;
            if (nums[0] <= nums[mid]) 
            {
                if (nums[0] <= target && target < nums[mid]) 
                {
                    r = mid - 1;
                }
                else 
                {
                    l = mid + 1;
                }
            }
            else 
            {
                if (nums[mid] < target && target <= nums[n - 1]) 
                {
                    l = mid + 1;
                }
                else 
                {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
};